package aufgabe1;



import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author benjamin
 */
public abstract class Tree<T> {

    protected Node _root;
    protected static final int BUFFER = 1024;
    protected int _nodes;
    protected int _leaves;
    protected int _depth;
    protected boolean _depthUpToDate = true;
    protected int _maxChildrens = 1;
    private TreeForm _tf;

    /**
     * Represent a tree node
     *
     * Every tree node has a value and some children's
     */
    protected class Node<T> {
        private T _value;
        private Node[] _childrens;
        private int _depthIndex = 1;

        /**
         * Constructor
         *
         * @param value - set value for this node
         */
        public Node(T value) {
            _childrens = new Node[_maxChildrens];
            _value = value;
            _leaves++;
            _nodes++;
        }

        
        /**
         * Returns current value
         *
         * @return
         */
        public T getValue() {
            return _value;
        }

        
        /**
         * Set children node at given index
         *
         * @param child
         * @param index
         */
        public void setChild(Node child, int index) {
            boolean before = isLeaf();
            _childrens[index] = child;
            boolean after = isLeaf();
            /*
             * Update leaf counter
             */
            if (after != before) {
                if (after) {
                    _leaves++;
                } else {
                    _leaves--;
                }
            }
            /*
             * Update depthIndex of child node
             */
            if (child != null) {
                child.setDepthIndex(_depthIndex + 1);
            }
        }

        
        /**
         * Get child node on given index
         *
         * @param index
         * @return
         */
        public Node<T> getChild(int index) {
            return _childrens[index];
        }

        
        /**
         * Set value of this node
         *
         * @param value
         */
        public void setValue(T value) {
            _value = value;
        }

        
        /**
         * Return the depth in tree of this node
         */
        public int getDepthIndex() {
            return _depth;
        }
        
        
        /**
         * Set the depthIndex of this node and update tree depth if necessary 
         * @param depth 
         */
        private void setDepthIndex(int depthIndex) {
            _depthIndex = depthIndex;
            if (_depth < depthIndex) {
                _depth = depthIndex;
            }
        }
                
        
        /**
         * Returns first free children index
         *
         * @return - if all childs are set, return value is -1
         */
        public int getFreeChildIndex() {
            for (int i = 0; i < _childrens.length; i++) {
                if (_childrens[i] == null) {
                    return i;
                }
            }
            return -1;
        }

        
        /**
         * Returns the maximal children count of this node
         *
         * @return
         */
        public int maxChildrens() {
            return _childrens.length;
        }

        /**
         * Returns true if node is a leaf
         *
         * @return
         */
        public boolean isLeaf() {
            for (int i = 0; i < _childrens.length; i++) {
                if (_childrens[i] != null) {
                    return false;
                }
            }
            return true;
        }
    }

    
    /**
     * Node Comparator
     * 
     * A encapsulated value comparator
     */
    protected class NodeComperator implements Comparator<Node> {
        private Comparator<T> _valueComparator;
        
        public NodeComperator(Comparator<T> valueComperator) {
            _valueComparator = valueComperator;
        }
        
        @Override
        public int compare(Node n1, Node n2) {
            return _valueComparator.compare((T)n1.getValue(), (T)n2.getValue());
        }
        
    }
    
    /**
     * Level by level iterator
     */
    private class LevelByLevelIterator implements Iterator<T> {

        private Queue<Node> _queue = new LinkedList<Node>();

        public LevelByLevelIterator() {
            _queue.add(_root);
        }

        @Override
        public boolean hasNext() {
            if (_queue.size() > 0) {
                return true;
            }
            return false;
        }

        @Override
        public T next() {
            Node<T> n = _queue.poll();
            buffer(n);
            return n.getValue();
        }

        @Override
        /**
         * Remove from a tree with iterator is not supported
         */
        public void remove() {
            throw new UnsupportedOperationException("Remove from a tree with iterator is not supported");
        }

        /**
         * Pre-buffering nodes to queue
         *
         * @param n - put all children's of n to queue
         */
        private void buffer(Node n) {
            for (int i = 0; i < _maxChildrens; i++) {
                Node m = n.getChild(i);
                if (m != null) {
                    _queue.add(m);
                }
            }
        }
    }

    /**
     * Adds a new value to this tree
     *
     * @param value
     */
    public void addValue(T value) {
        /*
         * Node to insert
         */
        Node n = new Node(value);
      
        if (_root == null) {
            /*
             * Tree is empty
             */
            _root = n;

        } else {
            /*
             * Add value on first possible place
             */

            Node[] queue = new Node[BUFFER];
            int parentIndex = -1;
            int workIndex = 0;
            int fillIndex = 0;
            queue[0] = _root;
            /*
             * Find first free place with Level-By-Level traversation
             */
            while (queue[workIndex] != null) {
                if (workIndex == fillIndex) {
                    if (fillIndex >= (queue.length - _maxChildrens - 2)) {
                        /*
                         * Extend queue
                         */
                        queue = extendArray(queue);
                    }
                    /*
                     * Fill queue
                     */
                    parentIndex++;
                    for (int i = 0; i < _maxChildrens; i++) {
                        queue[++fillIndex] = queue[parentIndex].getChild(i);
                    }
                }
                workIndex++;
            }

            /*
             * set parent child reference
             */
            int childIndex = queue[parentIndex].getFreeChildIndex();
            if (childIndex == -1) {
                throw new RuntimeException("Insert not possible: Determined place is no longer free!");
            }
            queue[parentIndex].setChild(n, childIndex);
        }

    }

    
    /**
     * Extends an array to its double size
     *
     * @param arr
     * @return
     */
    private Node[] extendArray(Node[] arr) {
        int len = arr.length;
        Node[] newArr = new Node[len * 2];
        System.arraycopy(arr, 0, newArr, 0, len);
        return newArr;
    }

    
    /**
     * Delete all equal values from this tree
     * @param value 
     */
    public void delValue(T value) {
        _depthUpToDate = false;
        delRecursive(_root, value, null, 0);
    }

    
    /**
     * Delete all values are equal to the given from this tree
     * 
     * Method is called from delValue
     * 
     * @param root - current / start node
     * @param value - value to compare
     * @param parent - parent node
     * @param index - current child index
     */
    private void delRecursive(Node root, T value, Node parent, int index) {
        if (root == null) {
            /*
             * stop recursion
             */
            return;
        }
        if (root.getValue().equals(value)) {
            /*
             * delete node
             */
            _nodes--;
                
            if (root.isLeaf()) {
                /*
                 * delete leaf
                 */
                if (parent != null) {
                    /*
                     * current node isn't root node
                     */
                    parent.setChild(null, index);
                } else {
                    /*
                     * node is root, update reference
                     */
                    _root = null;
                }
                _leaves--;
                
                
            } else {
                /*
                 * delete node, which has childs
                 */
                Node replaceNode = getNextLeaf(root, value, root, 0);
                if (parent != null) {
                    /*
                     * current node isn't root node
                     */
                    parent.setChild(replaceNode, index);
                } else {
                    /*
                     * current node is root node, update reference
                     */
                    _root = replaceNode;
                }
                if (replaceNode != null) {
                    /*
                     * transfer child references to replaceNode
                     */
                    for (int i = 0; i < _maxChildrens; i++) {
                        replaceNode.setChild(root.getChild(i), i);
                    }
                    if (replaceNode.isLeaf()) {
                        _leaves--;
                    }
                }
                /*
                 * set reference for next recursion step
                 */
                root = replaceNode;
            }
        }
        
        /*
         * recursion
         */
        for (int i = 0; i < _maxChildrens; i++) {
            delRecursive(root.getChild(i), value, root, i);   
        }
    }
    
    
    /**
     * Method used by delRecursive
     * 
     * Find the next leaf, which isn't equal to given value and return this leaf.
     * Reference to parent node will be removed
     * 
     * @param n - current node
     * @param value - value to compare
     * @param parent - parent node
     * @param index - child index
     * @return - leaf or null
     */
    private Node getNextLeaf(Node n, T value, Node parent, int index) {
        /**
         * stop recursion
         */
        if (n.isLeaf()) {
            /*
             * node is a leaf
             */
            if (!n.getValue().equals(value)) {
                /*
                 * leaf hasn't the given value
                 * delete parent reference and return leaf
                 */
                parent.setChild(null, index);
                return n;
            }
            return null;
        }
        
        /*
         * recursion
         */
        Node rv = null;
        for (int i = 0; i < _maxChildrens; i++) {
            Node m = n.getChild(i);
            if (m != null) {
                rv = getNextLeaf(m, value, n, i);
            }
            if (rv != null) {
                /*
                 * return first leaf
                 */
                return rv;
            }
        }
        /*
         * return null
         */
        return rv;
    }
    
    
    /**
     * Returns an iterator to traverse this tree level by level
     *
     * @return - iterator object
     */
    public Iterator<T> levelByLevelIterator() {
        return new LevelByLevelIterator();
    }

    
    /**
     * Show this tree as a graphic (JFrame)
     */
    public void showTreeGraphic(String title) {
        _tf = new TreeForm(_root, title);
    }
    
    
    public void updateTreeGraphic(String title) {
        _tf.update(_root, title);
    }

    /**
     * Returns the number of leaves in this tree
     *
     * @return
     */
    public int leaves() {
        return _leaves;
    }

    
    /**
     * Return the number of nodes in this tree
     *
     * @return
     */
    public int nodes() {
        return _nodes;
    }

    
    /**
     * Return depth of this tree
     * @return 
     */
    public int depth() {
        if (!_depthUpToDate) {
            _depthUpToDate = true;
            _depth = updateDepth(_root);
        }
        return _depth;
    }
    
    /**
     * 
     * @param n
     * @return 
     */
    private int updateDepth(Node n) {
        if (n == null) {
            return 0;
        }
        if (n.isLeaf()) {
            return n.getDepthIndex();
        }
        
        int depth = 0;
        int rv = 0;
        for (int i = 0; i < _maxChildrens; i++) {
            rv = updateDepth(n.getChild(i));
            if (rv > depth) {
                depth = rv;
            }
        }
        return depth;
    }
        
    
}
